package ahaArithmetic;

//城市地图-最短路径  深度优先解法
public class Dfs_5 {

    static int map[][] = new int[][]{
            {1,2,2},
            {1,5,10},
            {2,3,3},
            {2,5,7},
            {3,1,4},
            {3,4,4},
            {4,5,5},
            {5,3,3}
    };
    static int n = 5; //表示有五个城市
    static int map2[][] = new int[n][n];
    static int[] book = new int[n];
    static int min = 9999;

    public static void main(String[] args) {
        //初始化二维矩阵
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(j==k){
                    map2[j][k] = 0;
                    continue;
                }
                map2[j][k] = 9999;
            }
        }
        //给二维矩阵赋值
        for(int[] x:map){
            map2[x[0]-1][x[1]-1] = x[2];
        }

        dfs_5(0,0);
        System.out.println(min);
    }

    public static void dfs_5(int k,int dis){
        //判断是否超过最短路程
        if(dis>min){
            return;
        }
        //判断是否到达终点
        if(k==n-1){
            if(dis<min){
                min=dis;
                return;
            }
        }
        //标记为走过
        book[k] =1;
        //深度优先遍历
        for(int i=0;i<n;i++){
            if(map2[k][i]!=9999 && book[i]!=1){
                dfs_5(i,dis+map2[k][i]);
            }
        }
        //遍历结束 标记取消
        book[k] = 0;
    }

}

